package com.squirrel.michale;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个 n 个节点的带权无向图，节点编号为 0 到 n - 1 。
 *
 * 给你一个整数 n 和一个数组 edges ，其中 edges[i] = [ui, vi, wi] 表示节点 ui 和 vi 之间有一条权值为 wi 的无向边。
 *
 * 在图中，一趟旅途包含一系列节点和边。旅途开始和结束点都是图中的节点，且图中存在连接旅途中相邻节点的边。注意，一趟旅途可能访问同一条边或者同一个节点多次。
 *
 * 如果旅途开始于节点 u ，结束于节点 v ，我们定义这一趟旅途的 代价 是经过的边权按位与 AND 的结果。换句话说，如果经过的边对应的边权为 w0, w1, w2, ..., wk ，那么代价为w0 & w1 & w2 & ... & wk ，其中 & 表示按位与 AND 操作。
 *
 * 给你一个二维数组 query ，其中 query[i] = [si, ti] 。对于每一个查询，你需要找出从节点开始 si ，在节点 ti 处结束的旅途的最小代价。如果不存在这样的旅途，答案为 -1 。
 *
 * 返回数组 answer ，其中 answer[i] 表示对于查询 i 的 最小 旅途代价。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 5, edges = [[0,1,7],[1,3,7],[1,2,1]], query = [[0,3],[3,4]]
 *
 * 输出：[1,-1]
 *
 * 解释：
 *
 *
 *
 * 第一个查询想要得到代价为 1 的旅途，我们依次访问：0->1（边权为 7 ）1->2 （边权为 1 ）2->1（边权为 1 ）1->3 （边权为 7 ）。
 *
 * 第二个查询中，无法从节点 3 到节点 4 ，所以答案为 -1 。
 *
 * 示例 2：
 *
 * 输入：n = 3, edges = [[0,2,7],[0,1,15],[1,2,6],[1,2,1]], query = [[1,2]]
 *
 * 输出：[0]
 *
 * 解释：
 *
 *
 *
 * 第一个查询想要得到代价为 0 的旅途，我们依次访问：1->2（边权为 1 ），2->1（边权 为 6 ），1->2（边权为 1 ）。
 *
 * https://www.bilibili.com/video/BV1ut421H7Wv/?vd_source=dd94464bac13f791ea6a2e385d28295a  第四题
 *
 */
public class Day20240413_LeetCode003108 {

    public int[] minimumCost(int n, int[][] edges, int[][] query) {
        List<int[]>[] g = new ArrayList[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0], y = e[1], w = e[2];
            g[x].add(new int[]{y, w});
            g[y].add(new int[]{x, w});
        }

        int[] ids = new int[n]; // 记录每个点所在连通块的编号
        Arrays.fill(ids, -1);
        List<Integer> ccAnd = new ArrayList<>(); // 记录每个连通块的边权的 AND
        for (int i = 0; i < n; i++) {
            if (ids[i] < 0) {
                ccAnd.add(dfs(i, ccAnd.size(), g, ids));
            }
        }

        int[] ans = new int[query.length];
        for (int i = 0; i < query.length; i++) {
            int s = query[i][0], t = query[i][1];
            ans[i] = ids[s] != ids[t] ? -1 : ccAnd.get(ids[s]);
        }
        return ans;
    }

    private int dfs(int x, int curId, List<int[]>[] g, int[] ids) {
        ids[x] = curId; // 记录每个点所在连通块的编号
        int and = -1;
        for (int[] e : g[x]) {
            and &= e[1];
            if (ids[e[0]] < 0) { // 没有访问过
                and &= dfs(e[0], curId, g, ids);
            }
        }
        return and;
    }






}
